package main

import (
	"fmt"
)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type ListNode struct {
	Val  int
	Next *ListNode
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isSubPath(head *ListNode, root *TreeNode) bool {

	if head.Next == nil && head.Val == root.Val {
		return true
	}

	if root.Left == nil || root.Right == nil {
		return false
	}
	if head.Val == root.Val {
		if isSubPath(head.Next, root.Left) {
			return true
		}
		if isSubPath(head.Next, root.Right) {
			return true
		}

	} else {
		if isSubPath(head, root.Left) {
			return true
		}
		if isSubPath(head, root.Right) {
			return true
		}
	}
	return false

}

func main() {
	h := ListNode{Val: 2, Next: nil}
	t := TreeNode{Val: 1, Left: nil, Right: nil}
	fmt.Println(isSubPath(&h, &t))
}
